/*
 * @lc app=leetcode.cn id=213 lang=java
 *
 * [213] 打家劫舍 II
 */

// @lc code=start
class Solution {
    public int rob(int[] nums) {
        //这里其实相比较打家劫舍，需要考虑[0,nums.length-2]和[1,nums.length-1]两类情况
        if(nums.length==1) return nums[0];
        return Math.max(dp(nums,0,nums.length-2),dp(nums,1,nums.length-1));
    }
    
    public int dp(int[] nums,int start,int end){
        if(start==end) return nums[start];
        int[] dp=new int[end-start+1];
        dp[0]=nums[start];
        dp[1]=Math.max(nums[start],nums[start+1]);
        for(int i=2;i<dp.length;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+nums[start+i]);
        }
        return dp[dp.length-1];
    }
}
// @lc code=end

